package cn.zifangsky.sort;

/**
 * 桶排序
 *
 * @author zifangsky
 * @date 2019/1/10
 * @since 1.0.0
 */
public class BucketSort {

    /**
     * 桶排序
     * <p><b>时间复杂度：</b>O(1)</p>
     * <p><b>Note：</b>这个示例只能排序没有重复的一百以内的正整数</p>
     * @author zifangsky
     * @date 2019/1/10 14:21
     * @since 1.0.0
     * @param array 待排序数组
     */
    public static int[] sort(int[] array){
        int tempLength = 100;

        if(array == null || array.length < 1 || array.length > tempLength){
            throw new IllegalArgumentException("Illegal initial array");
        }

        int length = array.length;
        //临时数组
        int[] tempArray = new int[tempLength];

        //1. 第一次扫描待排序数组
        for(int i = 0; i < length; i++){
            tempArray[array[i]] = 1;
        }

        //2. 第二次扫描临时数组，取值
        for(int i = 0, j = 0; i < tempLength; i++){
            if(tempArray[i] == 1){
                array[j] = i;
                j++;
            }
        }

        return array;
    }


}
